package 二叉树;

/**
 * 559. Maximum Depth of N-ary Tree
 * https://leetcode.com/problems/maximum-depth-of-n-ary-tree/
 *
 * Given a n-ary tree, find its maximum depth.
 *
 * The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
 *
 * Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).
 *
 *
 * Example 1:
 *
 *           1
 *         / | \
 *        3  2  4
 *       / \
 *      5   6
 *
 * Input: root = [1,null,3,2,4,null,5,6]
 * Output: 3
 * Example 2:
 *
 *              1
 *        /  /  |   \
 *       2  3   4    5
 *         / \  |   / \
 *        6  7  8  9  10
 *           |  |  |
 *           11 12 13
 *           |
 *           14
 *
 * Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
 * Output: 5
 *
 * Constraints:
 * The depth of the n-ary tree is less than or equal to 1000.
 * The total number of nodes is between [0, 10^4].
 *
 * 类似：
 * E_104_二叉树的最大深度
 *
 */
public class E_559_N叉树的最大深度 {
    public int maxDepth(Node root) {
        if (root == null) return 0;
        int max = 0;
        for (Node node: root.children) {
            max = Math.max(max, maxDepth(node));
        }
        return max+1;
    }
}
